#include <stdio.h>
#include <stdlib.h>

//top变量时刻表示栈顶元素所在位置
int top=-1;
//二叉树节点结构
typedef struct binaryTreeNode {
    int data;   //数据域
    struct binaryTreeNode * leftChild, * rightChild;    //左右孩子指针
}binaryTreeNode_t, *binaryTree;

//初始化树的函数
void createBinaryTree(binaryTree * T){
    *T = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->data = 1;
    //根节点左孩子
    (*T)->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->leftChild = NULL;
    (*T)->leftChild->data = 2;
    (*T)->leftChild->rightChild = NULL;
    //根节点右孩子
    (*T)->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->leftChild = NULL;
    (*T)->rightChild->data = 3;
    (*T)->rightChild->rightChild = NULL;
    //根节点左孩子的左孩子
    (*T)->leftChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->leftChild->leftChild = NULL;
    (*T)->leftChild->leftChild->data = 4;
    (*T)->leftChild->leftChild->rightChild = NULL;
    //根节点左孩子的右孩子
    (*T)->leftChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->rightChild->leftChild = NULL;
    (*T)->leftChild->rightChild->data = 5;
    (*T)->leftChild->rightChild->rightChild = NULL;
    //根节点右孩子的左孩子
    (*T)->rightChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->leftChild->leftChild = NULL;
    (*T)->rightChild->leftChild->data = 6;
    (*T)->rightChild->leftChild->rightChild = NULL;
    //根节点右孩子的右孩子
    (*T)->rightChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->rightChild->leftChild = NULL;
    (*T)->rightChild->rightChild->data = 7;
    (*T)->rightChild->rightChild->rightChild = NULL;
}

//弹栈函数
void pop() {
    if(top == -1) {
        return;
    }
    top--;
}

//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(binaryTreeNode_t * elem) {
    printf("%d ", elem->data);
}

//后序遍历非递归算法
typedef struct SNode
{
    /* data */
    binaryTree bt;
    int tag;
}SNode_t;

//后序遍历使用的进栈函数
void push(SNode_t * a, SNode_t sdata) {
    a[++top] = sdata;
}

//后序遍历函数
void PostOrderTraverse(binaryTree Tree) {
    //定义一个顺序栈
    SNode_t a[20];
    //临时指针
    binaryTreeNode_t * p;
    int tag = -1;
    SNode_t sdata;
    p = Tree;
    while (p || top != -1)
    {
        /* code */
        while (p)
        {
            /* code */
            //为该结点入栈做准备
            sdata.bt = p;
            //由于遍历是左孩子，设置标志位为0
            sdata.tag = 0;
            //压栈
            push(a, sdata);
            //以该结点为根结点，遍历左孩子
            p = p->leftChild;
        }
        //取栈顶元素
        sdata = a[top];
        //栈顶元素弹栈
        pop();
        p = sdata.bt;
        tag = sdata.tag;
        //如果tag==0，说明该结点还没有遍历它的右孩子
        if (tag == 0)
        {
            /* code */
            sdata.bt = p;
            sdata.tag = 1;
            //更改该结点的标志位，重新压栈
            push(a, sdata);
            //以该结点的右孩子为根结点，重复循环
            p = p->rightChild;
        }
        //如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以调用操作函数了
        else {
            displayElem(p);
            p = NULL;
        }
    }
}


int main(int argc, char * argv[]) {
    binaryTree Tree;
    createBinaryTree(&Tree);
    printf("后序遍历1: \n");
    PostOrderTraverse(Tree);
    return 0;
}